import random
from tools_algorithm import *


class Solution:
    def minimumSubstringsInPartition(self, s: str) -> int:
        n = len(s)
        f = [inf] * n
        for i in range(n):
            mx, h = 0, Counter()
            for j in range(i, -1, -1):
                h[s[j]] += 1
                mx = max(mx, h[s[j]])
                if len(h) * mx == i - j + 1:
                    f[i] = min(f[i], f[j - 1] + 1 if j > 0 else 1)
        return f[n - 1]


h = {}
h.items()

s = Solution()
print(s.minimumSubstringsInPartition(s="abababaccddb"))

c = []
for _ in range(1000):
    c.append(chr(random.randint(ord("a"), ord("z"))))
print("".join(c))
